package com.AdvancedDemos.集合.单列集合;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LearnArrayListAndLinkedList {
    public static void main(String[] args) {
        /**
         * ArrayList底层是基于"数组"实现的
         * 因此根据索引随机访问数据,是非常快的
         * 删除效率低,因为需要挨个挪动数据
         * 添加效率也低,可能需要把很多数据后移,也可能需要数组扩容
         * 总结为:查询快,增删慢
         *
         * ArrayList集合的底层原理:
         * ①利用无参构造器创建的集合,会在底层创建一个默认长度为0的数组
         * ②添加add第一个元素,底层会创建一个新的长度为10的数组
         * ③当存满了,存第11个数据时,会新建一个数组扩容到1.5倍(即15),把原数据迁移到新数组,再存第11个数据
         * ④如果一次性添加addAll多个元素,1.5倍还放不下,则新建数值的长度以实际为准,如原长度为10,新添加11个数据,则新数组长度为21
         *
         * 如果使用带参的构造创建ArrayList集合对象,将根据参数元素的个数初化内部数组长度;再add单个元素时超出容量,会扩容到1.5倍;如果addAll多个元素超出了1.5倍扩容后的容量,则以当前实际总长度进行扩容
         */


        ArrayList<String> list = new ArrayList<>();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        System.out.println(list);//[1, 2, 3, 4]
        //ArrayList取子集合方法
        List<String> list1 = list.subList(0, 2);// public List<E> subList(int fromIndex, int toIndex) 包头不包尾
        System.out.println(list1);//[1, 2]


        /**
         * LinkedList底层是基于"双链表"实现的
         * 链表中的结点是独立的对象,在内存中是不连续的,每个结点包含数据值和下一个结点的地址
         * 单链表的特点:查询慢,需要从头开始遍历;但是增删相对快
         * 双链表的特点:对首尾元素进行增删改查的速度是极快的
         * 而LinkedList是基于双链表实现的,查询慢,需要从头开始遍历,但是增删相对快,对首尾元素进行增删改查的速度是极快的
         * 所以LinkedList有很多首尾操作的特有方法
         * 常常使用LinkedHashList来构建栈和队列的结构
         *
         * public void addFirst(E e) --- 在该列表开头插入指定的元素
         * public void addLast(E e) --- 在末尾追加指定的元素
         * public E getFirst() --- 返回列表中第一个元素
         * public E getLast() --- 返回列表中最后一个元素
         * public E removeFirst() --- 从此列表中删除并返回第一个元素
         * public E removeLast() --- 从此列表中删除并返回最后一个元素
         */


        //使用LinkedList实现队列 (默认尾进头出)
        LinkedList<String> queue = new LinkedList<>();
        //尾入队
        queue.addLast("第1号人");
        queue.addLast("第2号人");
        queue.addLast("第3号人");
        queue.addLast("第4号人");
        System.out.println(queue);//[第1号人, 第2号人, 第3号人, 第4号人]
        //头出队
        System.out.println(queue.removeFirst());//第1号人
        System.out.println(queue.removeFirst());//第2号人
        System.out.println(queue);//[第3号人, 第4号人]

        System.out.println("-----------------");
        //使用LinkedList实现栈 (默认头进头出)
        LinkedList<String> stack = new LinkedList<>();
        //压栈
        stack.addFirst("第1颗子弹");
        stack.addFirst("第2颗子弹");
        stack.push("第3颗子弹");//push中调用的就是addFirst
        stack.push("第4颗子弹");
        System.out.println(stack);//[第4颗子弹, 第3颗子弹, 第2颗子弹, 第1颗子弹]

        //出栈
        System.out.println(stack.removeFirst());//第4颗子弹
        System.out.println(stack.removeFirst());//第3颗子弹
        System.out.println(stack.pop());//第2颗子弹
        //pop当中就是调用的removeFirst
        System.out.println(stack);//[第1颗子弹]


    }
}
